1. Field of the Invention
The present invention relates to network congestion control. More specifically, the present invention relates to methods and apparatus for detecting and alleviating conditions such as deadlock.
2. Description of Related Art
Many conventional network protocols use packet dropping to alleviate congestion at a network node. In one example, a network node in an IP based network receives input data from multiple sources at a rate exceeding its output bandwidth. In conventional implementations, selected packets are dropped to allow transmission of remaining packets within the allocated output bandwidth. Packets can be dropped randomly or dropped using various selection criteria. The dropped packets are ultimately retransmitted under the control of a higher level protocol such as TCP.
In networks such as fibre channel networks, packet dropping is generally highly undesirable. Instead, networks such as fibre channel networks implement end-to-end and buffer-to-buffer flow control mechanisms. End-to-end and buffer-to-buffer flow control mechanisms do not allow a first network node to transmit to a second network node until a second network node is ready to receive a frame. The second network node typically indicates that it is ready to receive a frame by granting credits to the first network node. When frames are transmitted, credits are used. When no credits remain, the first network node can no longer transmit to the second network node. However, end-to-end and buffer-to-buffer flow control mechanisms provide only a very rough technique for controlling congestion, as the mechanism blocks all traffic along a particular link.
Such blocking can lead to deadlock, a situation where two or more switches are unable to transmit because the switches are no longer able to receive additional frames. For example, a first switch cannot transmit to a second switch because the second switch has a full buffer. However, buffer space cannot be freed until the second switch can transmit to the first switch that also has a full buffer. Blocking can also quickly propagate upstream to other links in a fibre channel network topology. Some of these links might serve as corridors for paths that do not include the originally congested link. Hence, congestion at one link of one network path can sometimes cause blocking over a much wider portion of a fibre channel topology.
It is therefore desirable to provide methods and apparatus for improving congestion control at networks nodes in a network such as a fibre channel network with respect to some or all of the performance limitations noted above.